package com.wyp168.leetcode.treenode;

import com.wyp168.leetcode.listnode.ListNode;

/**
 * @ClassName DeepestLeavesSum
 * @Description TODO  找到树结构中最深的叶子结点值的和
 * @Author wyp168
 * @Date 2022/8/17 08:23
 */
public class DeepestLeavesSum {

    int maxLevel = -1;
    int sum = 0;
    public static void main(String[] args) {
        DeepestLeavesSum deepestLeavesSum = new DeepestLeavesSum();
        TreeNode a = new TreeNode(1);
        TreeNode d = new TreeNode(7);
        TreeNode c = new TreeNode(4);
        c.setLeft(d);

        TreeNode cc = new TreeNode(5);
        TreeNode b = new TreeNode(2);
        b.setLeft(c);
        b.setRight(cc);

        TreeNode dd = new TreeNode(8);
        TreeNode ccc = new TreeNode(6);
        ccc.setRight(dd);
        TreeNode bb = new TreeNode(3);
        bb.setRight(ccc);
        a.setLeft(b);
        a.setRight(bb);

        System.out.println(deepestLeavesSum.deepestLeavesSum(a));
    }

    public int deepestLeavesSum(TreeNode root) {
        dfs(root, 0);
        return sum;
    }

    public void dfs (TreeNode node, int level) {
        if (node == null) {
            return;
        }
        if (maxLevel < level) {
            maxLevel = level;
            sum = node.val;
        } else if (maxLevel == level) {
            sum += node.val;
        }

        dfs(node.left, level +1);
        dfs(node.right, level + 1);
    }
}